1. Field of the Invention
The invention relates to compilers and pre-compilers, also called language re-writers, implementing methods for automated code conversion and to the methods themselves, the methods targeting a computation engine with a predefined architecture.
2. Description of the Related Technology
Before applications can be executed on a computation engine, also called computer system, the source code of the applications needs to be converted into a sequence of instructions, understood by the computation engine. This is performed in a compiler. A compiler is a computer program that translates text written in a first computer language, the source language which usually is a high-level programming language such as e.g. Fortran, Pascal or C, into a second computer language, the target language which usually is a lower level language such as e.g. assembly language or machine language. The input to the compiler is called the source code, and the output is called the object code.
Conversion methods or compilers exist for various computation engines, e.g. traditional compilers for computation engines based on a general purpose processor. Also vendors of other computation engines provide with their device a suitable compiler.
Sometimes, code is rewritten in a same language but in a different form. This is done in a language rewriter or pre-compiler, which is a program that translates the form of expressions without a change of language. This may for example be done to optimize code.
A VLIW (Very Long Instruction Word) processor executes instructions in parallel based on a fixed schedule determined when the program is compiled. Since determining the order of execution of instructions, including which instructions can execute simultaneously, is handled by the compiler, the processor does not need scheduling hardware. As a result, VLIW processors offer significant computational power with limited hardware complexity.
When scheduling instructions, a principle of locality, also called locality of reference, is used. This is the phenomenon that a same value or related storage location is frequently accessed. Different types of locality of reference are to be distinguished. In temporal locality, a resource that is referenced at one point in time is referenced again soon afterwards. In spatial locality, the likelihood of referencing a storage location is greater if a storage location near it has been recently referenced. Programs and systems which exhibit locality exhibit predictable behavior, and thus provide opportunities for designers to improve performance through pre-fetching, pre-computing and caching of code and data for future use.
In computer code, current state of the art techniques, used for example for regular processors like a Very Long Instruction Word (VLIW) processor connected to a scratch pad memory (SPM), exploit locality in only two ways:                1. Temporal Locality of the SPM or the register (register spilling): Prior art temporal locality of the SPM or the register (register allocation) looks at all the data on the scratch pad or the register, respectively, as a whole.        2. Spatial Locality of the SPM or the register: bring data accessed together in space.        
The register spilling problem has also been addressed by various research groups. These techniques once again look at singular registers instead of data arrays.
Current state of the art techniques perform optimizations that improve the spatial locality in the SPM only. This process improves the “layout locality” on a smaller part of a SPM in particular the line.